//空间复杂度：算法在运行过程中"临时占用存储空间大小的量度"
//注："空间复杂度算的时变量的个数"，而不是程序占用多少byte ->使用大O渐进法

#include <iostream>
#include <new>
#include <cassert>
using namespace std;

// 空间复杂度为：O(1) -> 变量的个数为常量(包含end、exchange和i)
void BubbleSort(int *a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])
            {
                // Swap(&a[i - 1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

//空间复杂度为：O(N) -> 动态开辟了N个空间
long long *Fibonacci(size_t n)
{
    if (n == 0)
        return NULL;
    long long *fibArray = new long long[n + 1];
}

//空间复杂度为：O(N) -> 递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间
long long Factorial(size_t N)
{
    return N < 2 ? N : Factorial(N - 1) * N;
}

//斐波拉契数使用递归求解时fib(n - 1) + fib(n - 2)
//空间复杂度为：O(N) -> 递归调用了N次，左边的递归结束后，右边的递归将覆盖左边被置为无效的空间，每个栈帧使用了常数个空间
//时间一去不复返，是累积的 <<>> 空间回收后可以重复利用

int main()
{
    system("pause");
    return 0;
}